The cyber-attack on an information system is rapidly increasing, and a countermeasure against the cyber-attack is required. As an intrusion route of the cyber-attack, a network and a USB memory are well known. Conventionally, as a technique for preventing the cyber-attack from the network, there is a packet filter. The packet filter has a mechanism to permit or deny a packet to pass in accordance with the rule set. The rule set consists of a condition to be satisfied by the packet and a rule describing an action of when the packet satisfies the condition. The action herein is to permit or deny the packet to pass. There is order in a sequence of rules within the rule set, and the packet is collated with the rule in accordance with the order. “The packet matches the rule” or “the packet and the rule much” means that the packet satisfies the condition described in the rule. When receiving the packet, the packet filter collates the packet with the rule in accordance with the order within the rule set. If the packet matches the rule, the packet is permitted or denied in accordance with the action defined in the rule. If the packet does not match the rule, it is continued to collate the packet with a next rule. At the end of the rule set, a rule called a default rule which matches all packets is set. Accordingly, even if the packet does not match any other rule, the packet is always processed by the default rule.
As the system and the attack on the system become more complicated, a corresponding rule set for packet filtering becomes larger. On the other hand, since the packet is collated with the rule one by one in accordance with the order, as the number of rules increases, in proportion to that, it takes longer to complete collation. Therefore, a technique for improving processing efficiency is necessary.
Patent Literature 1 discloses a technique for speeding up a packet filter by swapping order of rules within a rule set. An idea of Patent Literature 1 is to improve processing efficiency by moving a rule which matches a packet more frequently earlier in the order, and a rule which matches a packet less frequently later in the order. For that purpose, the rules are dynamically swapped in the rule set. That is, at a time of operating the packet filter, the number of times each rule matches a packet is recorded, and in accordance with that number of times, the rules are swapped. However, it is not allowed to result in changing meaning of the rule set by swapping the rules. Thus, only when two rules do not conflict with each other, these two rules are swapped. Here, the two rules are said to conflict with each other if actions of these rules are different, and if there is an overlap in any of conditions described in these rules. For example, a condition specified in a destination address is considered. If a range from 192.168.0.1 to 192.168.0.100 is described in a rule as a condition, and a range from 192.168.0.50 to 192.168.0.150 is described in other rule as a condition, these conditions are overlapped with each other.
Non-Patent Literature 1 discloses a technique for speeding up a packet filter by, before performing usual collation, performing other collation processing to filter out most of packets at high speed. If it is supposed that a rule is a logical expression and a bit string of a packet is a value to be substituted into the logical expression, the packet matches the rule only when a value of the logical expression is 1 and matching is limited at that time. Therefore, collation of the packet with the rule can be realized by the calculation of the logical expression. Hence, high speed collation can be realized by a data structure suitable for the calculation of the value of the logical expression. In Non-Patent Literature 1, the high speed collation is realized by a data structure which is a tree structure called a BDD. However, since a large storage area is necessary in order to represent the rule set using the BDD, it is difficult to represent the entire rule set using the BDD. Hence, scanning a tree of the BDD is terminated to a certain depth. This is performed as preprocessing of the original packet filter, the most of packets are filtered out, and the usual collation processing is performed on remaining packets. Thus, it is possible to shorten a time to process the entire packet filter.